package com.vilynn.learning.new2.question;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Matrix
 *
 * @author Weilin Wang
 * @since 2020/4/17
 *
 * 给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
 * 两个相邻元素间的距离为 1 。
 *
 */
public class Matrix {

    public static void main(String[] args) {
        int[][] a = new int[2][3];
        a[1][1] = 1;
        a[0][2] = 1;
        a[1][2] = 1;
        System.out.println(JSON.toJSONString(a));

        int[][] res = updateMatrix3(a);
        System.out.println(JSON.toJSONString(res));
    }

    public static int[][] updateMatrix(int[][] matrix) {
        int length = matrix.length;
        int[][] res = new int[length][];
        for(int i=0;i<length;i++){
            int size = matrix[i].length;
            res[i] = new int[size];
            for(int j=0;j<size;j++){
                if(matrix[i][j] == 0){
                    res[i][j] = 0;
                } else {
                    int min = -1;
                    for(int l=0;l<length;l++){
                        if(min == 1){
                            break;
                        }
                        int sizee = matrix[l].length;
                        for(int m=0;m<sizee;m++){
                            if(matrix[l][m] == 0){
                                int a = Math.abs(l-i)+Math.abs(m-j);
                                if(min == -1){
                                    min = a;
                                } else if(a < min){
                                    min = a;
                                }
                            }
                        }
                    }
                    res[i][j] = min;
                }
            }
        }
        return res;
    }

    public static int[][] updateMatrix2(int[][] matrix) {
        int length = matrix.length;
        int[][] res = new int[length][];
        List<String> finish = new ArrayList<>();
        for(int i=0;i<length;i++) {
            int size = matrix[i].length;
            res[i] = new int[size];
            for (int j = 0; j < size; j++) {
                if (matrix[i][j] == 0) {
                    res[i][j] = 0;
                    finish.add(i + "-" + j);
                }
            }
        }

        for(int i=0;i<length;i++) {
            int size = matrix[i].length;
            res[i] = new int[size];
            for (int j = 0; j < size; j++) {
                if (matrix[i][j] != 0) {
                    int min = -1;
                    for (String f : finish) {
                        int l = Integer.valueOf(f.split("-")[0]);
                        int m = Integer.valueOf(f.split("-")[1]);
                        int a = Math.abs(l-i)+Math.abs(m-j);
                        if(min == -1){
                            min = a;
                        } else if(a < min){
                            min = a;
                        }
                    }
                    res[i][j] = min;
                }
            }
        }
        return res;
    }

    public static int[][] updateMatrix3(int[][] matrix) {
        int length = matrix.length;
        int size = matrix[0].length;

        Queue<int[]> queue = new LinkedList();
        for(int i=0;i<length;i++) {
            for (int j = 0; j < size; j++) {
                if (matrix[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                }  else {
                   matrix[i][j] = -1;
                }
            }
        }

        int[] distx = new int[]{-1, 1, 0, 0};
        int[] disty = new int[]{0, 0, 1, -1};
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int i = poll[0];
            int j = poll[1];
            for (int move = 0; move < 4; move++) {
                int new_i = i + distx[move];
                int new_j = j + disty[move];
                if(new_i >= 0 && new_j >= 0
                        && new_i < length && new_j < size
                        && matrix[new_i][new_j] == -1){
                    matrix[new_i][new_j] = matrix[i][j] + 1;
                    queue.offer(new int[]{new_i, new_j});
                }
            }
        }
        return matrix;
    }
}
